#ifndef _LIST_H
#define _LIST_H

#include <stdlib.h>
#include <stdio.h>


template <class T>
class Link;
template <class T>
class Iterator;

template <class T>
class List
{
  public:
    List();
    List(int max_size);
    virtual ~List();
    void clear();
    virtual void insert(T val);
    virtual void flush(List<T> & list);
    void print();
    bool full() { return (this->MaxSize && this->Size==this->MaxSize);}
    bool empty() { return (this->Size==0);}
    int getSize();
    int getMaxSize() {return this->MaxSize;}
//   protected:
    void align();
    Link<T> * First;
    Link<T> * Last;
    int Size;
    int MaxSize;
};

template <class T>
class Link
{
  public:
    Link(T val,Link * next,Link * prev);
    ~Link();
    T Value;
    Link * Next;
    Link * Prev;    
    Link * insert(T value);
};

template <class T>
class Iterator
{
  public:
    Iterator();
    Iterator(const Iterator<T> & src);
    Iterator(List<T> * list);
    ~Iterator();
    virtual bool operator!=(Iterator<T> & itr);
    virtual bool operator==(Iterator<T> & itr);
    virtual bool operator++();
    virtual bool operator--();
    virtual T operator()();
    virtual int index();
    virtual bool operator!();
    virtual bool first();
    virtual bool last();
    virtual bool is_last();
    virtual bool is_first();
    
//   protected:
    List<T> * mList;
    Link<T> * current;
    Link<T> * next;
    Link<T> * prev;
};

/* List definitions */
template <class T>
List<T>::List() 
  : First(NULL),Last(NULL),Size(0),MaxSize(0){}

template <class T>
List<T>::List(int max_size)
  : First(NULL),Last(NULL),Size(0),MaxSize(max_size) {}

template <class T>
List<T>::~List()
{
  this->clear();
}

template <class T>
void List<T>::clear()
{
  Link<T> * next;
  for(Link<T> * p = this->First;p;p=next)
  {
    next = p->Next;
    delete p;
  }
  this->First=NULL;
  this->Last=NULL;
  this->Size=0;
}
template <class T>
void List<T>::flush(List<T> & list)
{
  if(list.getSize()==0)
    return;
  if(this->First==NULL)
  {
    this->First = list.First;
    this->Last = list.Last;
    list.First = NULL;
    list.Last = NULL;
    this->Size=list.Size;
  }
  else
  {
    this->Last->Next = list.First;
    list.First->Prev = this->Last;
    this->Last = list.Last;
    this->Size += list.Size;
  }
  if(this->MaxSize!=0)
    this->align();
  list.First = NULL;
  list.Last = NULL;
  list.Size=0;
}

template <class T>
void List<T>::align()
{
  while(this->Size > this->MaxSize)
  {
    Link<T> * toRemove = this->First;
    this->First = toRemove->Next;
    this->First->Prev=NULL;  
    delete toRemove; 
    this->Size--;
  }
}
template <class T>
void List<T>::insert(T val)
{
  if(this->First==NULL)
  {
      this->First = new Link<T>(val,NULL,NULL);
      this->Last = this->First;
      this->Size=1;
      return;
  }
  this->Last = this->Last->insert(val);
  if(this->MaxSize==0 || this->Size < this->MaxSize)
  {
    this->Size++;
    return;
  }
  Link<T> * toRemove = this->First;
  this->First = toRemove->Next;
  this->First->Prev=NULL;  
  delete toRemove;
}

template <class T>
int List<T>::getSize() {return this->Size;}

template <class T>
void List<T>::print()
{
  if(this->Size==0 || this->First==NULL || this->Last == NULL)
  {
   printf("Empty list\n");
   return;
  }
  printf("First = [%d]\n",this->First->Value);
  printf("Last = [%d]\n",this->Last->Value);
  for(Link<T> * p=this->First; p!=NULL ; p = p->Next)
  {
    printf("[");    
    if(p->Prev)
      printf("(%d)",p->Prev->Value);
    else
      printf("(N)");
    printf("<-(%d)->",p->Value);
    if(p->Next)
      printf("(%d)",p->Next->Value);
    else
      printf("(N)");
    printf("]");
    
  }
}

/* Link definitions */
template <class T>
Link<T>::Link(T val, Link<T>* next, Link<T>* prev)
  : Value(val),Next(next),Prev(prev){}

template <class T>
Link<T>::~Link()
{
//       printf(RED "Deleting %d\n" ENDCOLOR,this->Value);
}

template <class T>
Link<T> * Link<T>::insert(T val)
{
  this->Next = new Link<T>(val,this->Next,this);
  return this->Next;
}

/* Iterator definitions */
template <class T>
Iterator<T>::~Iterator()
{
 this->current=NULL;
 this->prev=NULL;
 this->next=NULL;
 this->mList=NULL; 
}
template <class T>
bool Iterator<T>::is_last()
{
  return (this->current && this->current == this->mList->Last);
}
template <class T>
bool Iterator<T>::is_first()
{
  return (this->current && this->current == this->mList->First);
}
template <class T>
Iterator<T>::Iterator(const Iterator<T> & src)
{
//   printf(YELLOW "COpy constructor\n"ENDCOLOR);
  this->mList = src.mList;
  this->current = src.current;
  this->prev=src.prev;
  this->next=src.next;
}
template <class T>
Iterator<T>::Iterator(List<T> * list)
  :current(NULL),next(NULL),prev(NULL)
{
 this->mList = list;
 this->first();
}

template <class T>
bool Iterator<T>::operator!=(Iterator<T> & itr)
{
  return (this->current != itr.current);
}

template <class T>
bool Iterator<T>::operator==(Iterator<T> & itr)
{
  return (this->current == itr.current);
}

template <class T>
bool Iterator<T>::operator++()
{
//   if(!this->current)
//     return false;
//   this->prev=this->current;
//   this->current = this->current->Next;
//   if(this->current)
//     this->next = this->current->Next;
//   else
//     this->next=NULL;
  this->current = this->current->Next;
  return true;
}
template <class T>
bool Iterator<T>::operator--()
{
  if(!this->current)
    return false;
  this->next=this->current;
  this->current = this->current->Prev;
  if(this->current)
    this->prev = this->current->Prev;
  else
    this->prev=NULL;
  return true;
}
template <class T>
T Iterator<T>::operator()()
{
//   if(this->current)
    return this->current->Value;
//   else
//   {
//       printf(RED "Iterator: operator(): this->current==NULL"ENDCOLOR);
//       exit(1);
//   }
//   return 0;
}
template <class T>
bool Iterator<T>::first()
{
  if(this->mList->First==NULL)
    return false;
  this->current = this->mList->First;
  this->next=this->current->Next;
  this->prev=this->current->Prev;
  return true;
}
template <class T>
bool Iterator<T>::last()
{
  if(this->mList->Last==NULL)
    return false;
  this->current = this->mList->Last;
  this->next=this->current->Next;
  this->prev=this->current->Prev;
  return true;
}

template <class T>
bool Iterator<T>::operator!()
{
  return (this->current != NULL);
}
template <class T>
int Iterator<T>::index()
{
  if(this->current==NULL)
    return -1;
  Link<T> * p = this->mList->First;
  int i=0;
  while(p != this->current)
  {
    i++;
    p = p->Next;
  }
  return i;
}

#endif //_LIST_H